package dp;

import java.util.Arrays;

public class D230819 {
    // 兑换零钱(一)
    // 时间：O(arr.length x aim)
    // 空间：O(aim)
    public int minMoney (int[] arr, int aim) {
        // 小于1的都返回0
        if(aim < 1) return 0;
        // dp[i]表示凑齐i元最少需要多少货币数
        int[] dp = new int[aim + 1];
        // 初始化，填充 aim + 1 最大值，
        // 这个是不可能的货币数，如果最终结果是这个值，说明无解
        Arrays.fill(dp, aim + 1);
        dp[0] = 0;

        for (int i = 1; i <= aim; i++) {
            // 遍历货币数组
            for (int j = 0; j < arr.length; j++) {
                // 维护最小值
                if(arr[j] <= i) dp[i] = Math.min(dp[i], dp[i - arr[j]] + 1);
            }
        }
        return dp[aim] > aim ? -1 : dp[aim];
    }


    // 最长上升子序列(一)
    // 时间：O(N2)
    // 空间：O(N)
    public int LIS (int[] arr) {
        if (arr.length == 0) return 0;
        // dp[i] 表示前 i 个数，最长上升子序列的长度
        int[] dp = new int[arr.length];
        // 最长子序列最少为 1
        Arrays.fill(dp, 1);
        int res = 1;
        for (int i = 1; i < arr.length; i++) {
            for (int j = 0; j < i; j++) {
                if (arr[i] > arr[j]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                    res = Math.max(dp[i], res);
                }
            }
        }
        return res;
    }



    // 连续子数组的最大和
    // 时间：O(N)
    // 空间：O(N)
    public int FindGreatestSumOfSubArray (int[] array) {
        // dp[i] 表示以下标 i 为终点，连续子数组的最大和
        int n = array.length;
        int[] dp = new int[n];
        dp[0] = array[0];
        int res = dp[0];
        for (int i = 1; i < n; i++) {
            // 当前值本身 与 当前值+前面子数组的和 取较大值
            dp[i] = Math.max(dp[i - 1] + array[i], array[i]);
            // 维护最大值
            res = Math.max(res, dp[i]);
        }
        return res;
    }

    // 空间优化
    // 时间：O(N)
    // 空间：O(N)
    // 使用两个变量来迭代 来代替 数组
    public int FindGreatestSumOfSubArray2 (int[] array) {
        // dp[i] 表示以下标 i 为终点，连续子数组的最大和
        int n = array.length;
        int[] dp = new int[n];
        int res = array[0];
        int x = array[0];
        int y = 0;
        // x 表示下标 i - 1 结尾，连续子数组的最大和
        // y 表示下标 i 结尾，连续子数组的最大和
        for (int i = 1; i < n; i++) {
            // 当前值本身 与 当前值+前面子数组的和 取较大值
            y = Math.max(x + array[i], array[i]);
            // 维护最大值
            res = Math.max(res, y);
            // 更新 x 的状态
            x = y;
        }
        return res;
    }
}
